//3286. 穿越网格图的安全路径

//给你一个 m x n 的二进制矩形 grid 和一个整数 health 表示你的健康值。
//你开始于矩形的左上角(0, 0) ，你的目标是矩形的右下角(m - 1, n - 1) 。
//你可以在矩形中往上下左右相邻格子移动，但前提是你的健康值始终是 正数 。
//对于格子(i, j) ，如果 grid[i][j] = 1 ，那么这个格子视为 不安全 的，会使你的健康值减少 1 。
//如果你可以到达最终的格子，请你返回 true ，否则返回 false 。
//注意 ，当你在最终格子的时候，你的健康值也必须为 正数 。

//class Solution {
//    static constexpr array<array<int, 2>, 4> dirs = { {{0, 1}, {0, -1}, {1, 0}, {-1, 0}} };
//public:
//    bool findSafeWalk(vector<vector<int>>& grid, int health) {
//        int m = grid.size(), n = grid[0].size();
//        vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
//        dis[0][0] = grid[0][0];
//        deque<pair<int, int>> q;
//        q.emplace_front(0, 0);
//        while (!q.empty()) {
//            auto [i, j] = q.front();
//            q.pop_front();
//            for (auto& [dx, dy] : dirs) {
//                int x = i + dx, y = j + dy;
//                if (0 <= x && x < m && 0 <= y && y < n) {
//                    int cost = grid[x][y];
//                    if (dis[i][j] + cost < dis[x][y]) {
//                        dis[x][y] = dis[i][j] + cost;
//                        cost == 0 ? q.emplace_front(x, y) : q.emplace_back(x, y);
//                    }
//                }
//            }
//        }
//        return dis[m - 1][n - 1] < health;
//    }
//};

//2290. 到达角落需要移除障碍物的最小数目

//给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n 。每个单元格都是两个值之一：
//0 表示一个 空 单元格，
//1 表示一个可以移除的 障碍物 。
//你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。
//现在你需要从左上角(0, 0) 移动到右下角(m - 1, n - 1) ，返回需要移除的障碍物的 最小 数目。

//class Solution {
//    static constexpr array<array<int, 2>, 4> dirs = { {{0, 1}, {0, -1}, {1, 0}, {-1, 0}} };
//public:
//    int minimumObstacles(vector<vector<int>>& grid) {
//        int m = grid.size(), n = grid[0].size();
//        vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
//        dis[0][0] = 0;
//        deque<pair<int, int>> q;
//        q.emplace_front(0, 0);
//        while (!q.empty()) {
//            auto [i, j] = q.front();
//            q.pop_front();
//            for (auto& [dx, dy] : dirs) {
//                int x = i + dx, y = j + dy;
//                if (0 <= x && x < m && 0 <= y && y < n) {
//                    int g = grid[x][y];
//                    if (dis[i][j] + g < dis[x][y]) {
//                        dis[x][y] = dis[i][j] + g;
//                        //需要破墙的在后，不需要的在前
//                        g == 0 ? q.emplace_front(x, y) : q.emplace_back(x, y);
//                    }
//                }
//            }
//        }
//        return dis[m - 1][n - 1];
//    }
//};

//1368. 使网格图至少有一条有效路径的最小代价

//给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：
//1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]
//2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]
//3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]
//4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]
//注意网格图中可能会有 无效数字 ，因为它们可能指向 grid 以外的区域。
//一开始，你会从最左上角的格子(0, 0) 出发。我们定义一条 有效路径 为从格子(0, 0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子(m - 1, n - 1) 结束的路径。
//有效路径 不需要是最短路径 。
//你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字 只能修改一次 。
//请你返回让网格图至少有一条有效路径的最小代价。

//class Solution {
//private:
//    static constexpr array<array<int, 2>, 4> dirs = { {{0, 1}, {0, -1}, {1, 0}, {-1, 0}} };
//public:
//    int minCost(vector<vector<int>>& grid) {
//        int m = grid.size(), n = grid[0].size();
//        vector<int> dist(m * n, INT_MAX);
//        vector<int8_t> vis(m * n);
//        dist[0] = 0;
//        deque<int> q;
//        q.push_back(0);
//
//        while (!q.empty()) {
//            auto cur_pos = q.front();
//            q.pop_front();
//            if (vis[cur_pos]) {
//                continue;
//            }
//            vis[cur_pos] = 1;
//            int x = cur_pos / n, y = cur_pos % n, i = -1;
//            for (const auto& [dx, dy] : dirs) {
//                int nx = x + dx, ny = y + dy;
//                int new_pos = nx * n + ny;
//                i++;
//                int new_dis = dist[cur_pos] + (grid[x][y] != i + 1);
//                if (nx >= 0 && nx < m && ny >= 0 && ny < n && new_dis < dist[new_pos]) {
//                    dist[new_pos] = new_dis;
//                    grid[x][y] == i + 1 ? q.push_front(new_pos) : q.push_back(new_pos);
//                }
//            }
//        }
//
//        return dist[m * n - 1];
//    }
//};

//3552. 网格传送门旅游

//给你一个大小为 m x n 的二维字符网格 matrix，用字符串数组表示，其中 matrix[i][j] 表示第 i 行和第 j 列处的单元格。每个单元格可以是以下几种字符之一：
//'.' 表示一个空单元格。
//'#' 表示一个障碍物。
//一个大写字母（'A' 到 'Z'）表示一个传送门。
//你从左上角单元格(0, 0) 出发，目标是到达右下角单元格(m - 1, n - 1)。你可以从当前位置移动到相邻的单元格（上、下、左、右），移动后的单元格必须在网格边界内且不是障碍物。
//如果你踏入一个包含传送门字母的单元格，并且你之前没有使用过该传送门字母，你可以立即传送到网格中另一个具有相同字母的单元格。这次传送不计入移动次数，但每个字母对应的传送门在旅程中 最多 只能使用一次。
//返回到达右下角单元格所需的 最少 移动次数。如果无法到达目的地，则返回 - 1。

//class Solution {
//    static constexpr array<array<int, 2>, 4> dirs = { {{0, 1}, {0, -1}, {1, 0}, {-1, 0}} };
//public:
//    int minMoves(vector<string>& matrix) {
//        int m = matrix.size(), n = matrix[0].size();
//        if (matrix[m - 1][n - 1] == '#') {
//            return -1;
//        }
//
//        vector<pair<int, int>> pos[26]{};
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                char c = matrix[i][j];
//                if (isupper(c)) {
//                    pos[c - 'A'].emplace_back(i, j);
//                }
//            }
//        }
//
//        vector dis(m, vector<int>(n, INT_MAX));
//        dis[0][0] = 0;
//        deque<pair<int, int>> q{ {0, 0} };
//
//        while (!q.empty()) {
//            auto [x, y] = q.front();
//            q.pop_front();
//            int d = dis[x][y];
//
//            if (x == m - 1 && y == n - 1) {
//                return d;
//            }
//
//            char c = matrix[x][y];
//            if (c != '.') {
//                // 使用所有传送门
//                for (auto& [px, py] : pos[c - 'A']) {
//                    if (d < dis[px][py]) {
//                        dis[px][py] = d;
//                        q.emplace_front(px, py);
//                    }
//                }
//                pos[c - 'A'].clear(); // 避免重复使用传送门
//            }
//
//            for (auto& [dx, dy] : dirs) {
//                int nx = x + dx, ny = y + dy;
//                if (0 <= nx && nx < m && 0 <= ny && ny < n && matrix[nx][ny] != '#' && d + 1 < dis[nx][ny]) {
//                    dis[nx][ny] = d + 1;
//                    q.emplace_back(nx, ny);
//                }
//            }
//        }
//
//        return -1;
//    }
//};

//1824. 最少侧跳次数

//给你一个长度为 n 的 3 跑道道路 ，它总共包含 n + 1 个 点 ，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道 出发 ，它想要跳到点 n 处。然而道路上可能有一些障碍。
//给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles[i] （取值范围从 0 到 3）表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ，那么点 i 处没有障碍。
//任何一个点的三条跑道中 最多有一个 障碍。
//比方说，如果 obstacles[2] == 1 ，那么说明在点 2 处跑道 1 有障碍。
//这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。
//为了躲避障碍，这只青蛙也可以在 同一个 点处 侧跳 到 另外一条 跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。
//比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。
//这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的 任一跑道 ，请你返回 最少侧跳次数 。
//注意：点 0 处和点 n 处的任一跑道都不会有障碍。

//class Solution {
//public:
//    int minSideJumps(vector<int>& obstacles) {
//        int n = obstacles.size();
//        vector<int> dis(n * 3, 0x3f3f3f3f);
//        dis[1] = 0;
//        deque<pair<int, int>> q;
//        q.emplace_back(0, 1); // 起点
//        while (true) {
//            auto [i, j] = q.front();
//            q.pop_front();
//            int d = dis[i * 3 + j];
//            if (i == n - 1) return d; // 到达终点
//            int idx = (i + 1) * 3 + j;
//            if (obstacles[i + 1] != j + 1 && d < dis[idx]) { // 向右
//                dis[idx] = d;
//                q.emplace_front(i + 1, j); // 加到队首
//            }
//            for (int k : {(j + 1) % 3, (j + 2) % 3}) // 枚举另外两条跑道（向上/向下）
//                if (obstacles[i] != k + 1 && d + 1 < dis[i * 3 + k]) {
//                    dis[i * 3 + k] = d + 1;
//                    q.emplace_back(i, k); // 加到队尾
//                }
//        }
//    }
//};

//LCP 56. 信物传送

//欢迎各位勇者来到力扣城，本次试炼主题为「信物传送」。
//本次试炼场地设有若干传送带，matrix[i][j] 表示第 i 行 j 列的传送带运作方向，"^", "v", "<", ">" 这四种符号分别表示 上、下、左、右 四个方向。
//信物会随传送带的方向移动。勇者每一次施法操作，可临时变更一处传送带的方向，在物品经过后传送带恢复原方向。lcp(2).gif
//通关信物初始位于坐标 start处，勇者需要将其移动到坐标 end 处，请返回勇者施法操作的最少次数。
//注意：start 和 end 的格式均为[i, j]

//class Solution {
//public:
//    int conveyorBelt(vector<string>& matrix, vector<int>& start, vector<int>& end) {
//        int n = matrix.size(), m = matrix[0].size();
//        vector<vector<int>> dis(n, vector<int>(m, INT_MAX));
//        deque<pair<int, int>> q;
//
//        // 方向数组：上、下、左、右
//        vector<int> dx = { -1, 1, 0, 0 };
//        vector<int> dy = { 0, 0, -1, 1 };
//        char dir[4] = { '^', 'v', '<', '>' };
//
//        q.emplace_front(start[0], start[1]);
//        dis[start[0]][start[1]] = 0;
//
//        while (!q.empty()) {
//            auto [x, y] = q.front();
//            q.pop_front();
//            if (x == end[0] && y == end[1]) return dis[x][y];
//            int weigh = dis[x][y];
//
//            // 遍历四个方向
//            for (int i = 0; i < 4; ++i) {
//                int nx = x + dx[i], ny = y + dy[i];
//                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
//                    int cost = (matrix[x][y] == dir[i]) ? 0 : 1;
//                    if (dis[nx][ny] > weigh + cost) {
//                        dis[nx][ny] = weigh + cost;
//                        cost == 0 ? q.emplace_front(nx, ny) : q.emplace_back(nx, ny);
//                    }
//                }
//            }
//        }
//        return -1;
//    }
//};